package leetcodev1.树;

public class LeetCode114 {

    //1.将左子树打平成一个链表后，插入到节点和右节点间
    //2.使用前序遍历后，组装成一个链表
    public void flatten(TreeNode root) {
        formatTree2LinkList(root);
    }

    private TreeNode formatTree2LinkList(TreeNode node) {
        if (node == null) {
            return node;
        }

        if (node.left == null && node.right == null) {
            return node;
        }

        TreeNode leftLinkList = formatTree2LinkList(node.left);
        TreeNode rightLinkList = formatTree2LinkList(node.right);
        if (leftLinkList != null) {
            node.left = null;
            node.right = leftLinkList;
            while (leftLinkList.right != null) {
                leftLinkList = leftLinkList.right;
            }
            leftLinkList.right = rightLinkList;
        } else {
            node.right = rightLinkList;
        }

        return node;
    }


    //error
//    private TreeNode formatTree2LinkList(TreeNode node) {
//        if (node == null) {
//            return null;
//        }
//
//        if (node.left == null) {
//            return node;
//        }
//
//        TreeNode right = node.right;
//        TreeNode LinkList = formatTree2LinkList(node.left);
//        if (LinkList != null) {
//            node.right = LinkList;
//            node.right.right = formatTree2LinkList(right);
//        } else {
//            node.right = formatTree2LinkList(node.right);
//        }
//
//        return node;
//    }
}
